SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>C4.5 algorithm</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">C4.5 algorithm</span></span>

</h1>

</header>

<p><b>C4.5</b> is an algorithm used to generate a <a href="Decision_tree" title="Decision tree">decision tree</a> developed by <a href="Ross_Quinlan" title="Ross Quinlan">Ross Quinlan</a>.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> C4.5 is an extension of Quinlan's earlier <a href="ID3_algorithm" title="ID3 algorithm">ID3 algorithm</a>. The decision trees generated by C4.5 can be used for classification, and for this reason, C4.5 is often referred to as a <a href="Statistical_classification" title="Statistical classification">statistical classifier</a>. In 2011, authors of the <a href="Weka_(machine_learning)" class="mw-redirect" title="Weka (machine learning)">Weka</a> machine learning software described the C4.5 algorithm as "a landmark decision tree program that is probably the machine learning workhorse most widely used in practice to date".<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p><p>It became quite popular after ranking #1 in the <i>Top 10 Algorithms in Data Mining</i> pre-eminent paper published by <a href="Springer_Science%2BBusiness_Media" title="Springer Science+Business Media">Springer</a> <a href="Lecture_Notes_in_Computer_Science" title="Lecture Notes in Computer Science">LNCS</a> in 2008.<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Algorithm">Algorithm</h2></div>

<p>C4.5 builds decision trees from a set of training data in the same way as <a href="ID3_algorithm" title="ID3 algorithm">ID3</a>, using the concept of <a href="Entropy_(information_theory)" title="Entropy (information theory)">information entropy</a>. The training data is a set <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S={s_{1},s_{2},...}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S={s_{1},s_{2},...}}</annotation>

</semantics>

</math></span><img src="./8492789852e28f64dc12a066472743034eca73b2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.67ex; height:2.509ex;" alt="{\displaystyle S={s_{1},s_{2},...}}" loading="lazy"></span> of already classified samples. Each sample <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s_{i}}</annotation>

</semantics>

</math></span><img src="./cfda82668232cbdc0874ed28ab8b6079420d1ffe.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.89ex; height:2.009ex;" alt="{\displaystyle s_{i}}" loading="lazy"></span> consists of a p-dimensional vector <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x_{1,i},x_{2,i},...,x_{p,i})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x_{1,i},x_{2,i},...,x_{p,i})}</annotation>

</semantics>

</math></span><img src="./2f17cc7c8a96a165460deb4261b98da81ce21883.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:18.244ex; height:3.009ex;" alt="{\displaystyle (x_{1,i},x_{2,i},...,x_{p,i})}" loading="lazy"></span>, where the <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{j}}</annotation>

</semantics>

</math></span><img src="./5db47cb3d2f9496205a17a6856c91c1d3d363ccd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.239ex; height:2.343ex;" alt="{\displaystyle x_{j}}" loading="lazy"></span> represent attribute values or <a href="Feature_(machine_learning)" title="Feature (machine learning)">features</a> of the sample, as well as the class in which <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s_{i}}</annotation>

</semantics>

</p><p>At each node of the tree, C4.5 chooses the attribute of the data that most effectively splits its set of samples into subsets enriched in one class or the other. The splitting criterion is the normalized <a href="Information_gain_in_decision_trees" class="mw-redirect" title="Information gain in decision trees">information gain</a> (difference in entropy). The attribute with the highest normalized information gain is chosen to make the decision. The C4.5 algorithm then <a href="Recursion_(computer_science)" title="Recursion (computer science)">recurses</a> on the <a href="Partition_of_a_set" title="Partition of a set">partitioned</a> sublists.

</p><p>This algorithm has a few <a href="Base_case_(recursion)" class="mw-redirect" title="Base case (recursion)">base cases</a>.

</p>

<ul><li>All the samples in the list belong to the same class. When this happens, it simply creates a leaf node for the decision tree saying to choose that class.</li>

<li>None of the features provide any information gain. In this case, C4.5 creates a decision node higher up the tree using the expected value of the class.</li>

<li>Instance of previously unseen class encountered. Again, C4.5 creates a decision node higher up the tree using the expected value.</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Pseudocode">Pseudocode</h3></div>

<p>In <a href="Pseudocode" title="Pseudocode">pseudocode</a>, the general algorithm for building decision trees is:<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup>

</p>

<ol><li>Check for the above base cases.</li>

<li>For each attribute <i>a</i>, find the normalized information gain ratio from splitting on <i>a</i>.</li>

<li>Let <i>a_best</i> be the attribute with the highest normalized information gain.</li>

<li>Create a decision <i>node</i> that splits on <i>a_best</i>.</li>

<li>Recurse on the sublists obtained by splitting on <i>a_best</i>, and add those nodes as children of <i>node</i>.</li></ol>

<div class="mw-heading mw-heading2"><h2 id="Implementations">Implementations</h2></div>

<p><b>J48</b> is an <a href="Open_source" title="Open source">open source</a> <a href="Java_(programming_language)" title="Java (programming language)">Java</a> implementation of the C4.5 algorithm in the <a href="Weka_(machine_learning)" class="mw-redirect" title="Weka (machine learning)">Weka</a> <a href="Data_mining" title="Data mining">data mining</a> tool.

</p>

<div class="mw-heading mw-heading2"><h2 id="Improvements_from_ID3_algorithm">Improvements from ID3 algorithm</h2></div>

<p>C4.5 made a number of improvements to ID3. Some of these are:

</p>

<ul><li>Handling both continuous and discrete attributes - In order to handle continuous attributes, C4.5 creates a threshold and then splits the list into those whose attribute value is above the threshold and those that are less than or equal to it.<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup></li>

<li>Handling training data with missing attribute values - C4.5 allows attribute values to be marked as ? for missing. Missing attribute values are simply not used in gain and entropy calculations.</li>

<li>Handling attributes with differing costs.</li>

<li>Pruning trees after creation - C4.5 goes back through the tree once it's been created and attempts to remove branches that do not help by replacing them with leaf nodes.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Improvements_in_C5.0/See5_algorithm">Improvements in C5.0/See5 algorithm</h2></div>

<p>Quinlan went on to create C5.0 and See5 (C5.0 for Unix/Linux, See5 for Windows) which he markets commercially. C5.0 offers a number of improvements on C4.5. Some of these are:<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup>

</p>

<ul><li>Speed - C5.0 is significantly faster than C4.5 (several orders of magnitude)</li>

<li>Memory usage - C5.0 is more memory efficient than C4.5</li>

<li>Smaller decision trees - C5.0 gets similar results to C4.5 with considerably smaller decision trees.</li>

<li>Support for <a href="Boosting_(machine_learning)" title="Boosting (machine learning)">boosting</a> - Boosting improves the trees and gives them more accuracy.</li>

<li>Weighting - C5.0 allows you to weight different cases and misclassification types.</li>

<li>Winnowing - a C5.0 option automatically <a href="Winnow_(algorithm)" title="Winnow (algorithm)">winnows</a> the attributes to remove those that may be unhelpful.</li></ul>

<p>Source for a single-threaded Linux version of C5.0 is available under the <a href="GNU_General_Public_License" title="GNU General Public License">GNU General Public License</a> (GPL).

</p>

<ul><li><a href="ID3_algorithm" title="ID3 algorithm">ID3 algorithm</a></li>

<li><a rel="nofollow" class="external text" href="http://timesleuth-rule.sourceforge.net">Modifying C4.5 to generate temporal and causal rules</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

<li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text">Quinlan, J. R. C4.5: <i>Programs for Machine Learning</i>. Morgan Kaufmann Publishers, 1993.</span>

</li>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFIan_H._WittenEibe_FrankMark_A._Hall2011" class="citation web cs1">Ian H. Witten; Eibe Frank; Mark A. Hall (2011). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20201127014857/https://www.cs.waikato.ac.nz/~ml/weka/book.html">"Data Mining: Practical machine learning tools and techniques, 3rd Edition"</a>. Morgan Kaufmann, San Francisco. p. 191. Archived from <a rel="nofollow" class="external text" href="http://www.cs.waikato.ac.nz/~ml/weka/book.html">the original</a> on 2020-11-27<span class="reference-accessdate">. Retrieved <span class="nowrap">2017-07-04</span></span>.</cite></span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><a rel="nofollow" class="external text" href="http://www.cs.umd.edu/~samir/498/10Algorithms-08.pdf">Umd.edu - Top 10 Algorithms in Data Mining</a></span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text">S.B. Kotsiantis, "Supervised Machine Learning: A Review of Classification Techniques", <i>Informatica</i> 31(2007) 249-268, 2007</span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text">J. R. Quinlan. Improved use of continuous attributes in c4.5. Journal of Artificial Intelligence Research, 4:77-90, 1996.</span>

</li>

<li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><a rel="nofollow" class="external text" href="http://www.rulequest.com/see5-comparison.html">Is See5/C5.0 Better Than C4.5?</a></span>

</li>

<li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text">M. Kuhn and K. Johnson, Applied Predictive Modeling, Springer 2013</span>

</li>

</ol></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li>Original implementation on Ross Quinlan's homepage: <a rel="nofollow" class="external text" href="http://www.rulequest.com/Personal/">http://www.rulequest.com/Personal/</a></li>

This article is issued from <a class="external text" title="Last edited on 2025-07-18" href="https://en.wikipedia.org/wiki/?title=C4.5_algorithm&oldid=1301122588">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>